import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: Solution_216
 * @Description:
 * 找出所有相加之和为 n 的 k 个数的组合。组合中只允许含有 1 - 9 的正整数，并且每种组合中不存在重复的数字。
 *
 * 说明：
 *
 * 所有数字都是正整数。
 * 解集不能包含重复的组合。 
 * 示例 1:
 *
 * 输入: k = 3, n = 7
 * 输出: [[1,2,4]]
 * 示例 2:
 *
 * 输入: k = 3, n = 9
 * 输出: [[1,2,6], [1,3,5], [2,3,4]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/combination-sum-iii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @Date: 2020/9/11 16:41
 * @Author: Song JinGen
 */
public class solution216 {
    public static List<List<Integer>> combinationSum3(int k, int n) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        ArrayList<Integer> templist = new ArrayList<Integer>();
        combinationSum(res, templist, k, n, 1);
        return res;
    }

    /**
     * 回溯算法
     *
     * @param res      结果集
     * @param templist 临时存放list
     * @param k        还需要几步递归结束
     * @param n        对于目前还有k步的情况下，需要得到的和为n
     * @param from     为了保证每个组合中都不存在重复，需要从from开始选择数字
     */
    private static void combinationSum(List<List<Integer>> res, ArrayList<Integer> templist, int k, int n, int from) {
        if (n < 0) {
            return;
        }
        //走到这一步一定需要return
        if (k == 0) {
            if (n == 0) {
                res.add(new ArrayList<Integer>(templist));//需要new一个新的list
                System.out.println("符合条件的数据" + res);
            }
            return;
        }
        //为了保证每个组合中都不存在重复，需要从from开始选择数字，最后结束选择的范围是9 - k + 1
        for (int i = from; i <= 9 - k + 1; i++) {
            templist.add(i);
            System.out.println("回溯前"+templist);
            combinationSum(res, templist, k - 1, n - i, i + 1);
            templist.remove(templist.size() - 1);//回溯算法常规步骤
            System.out.println("回溯后"+templist);
        }
    }

    public static void main(String[] args) {
        List<List<Integer>> lists = combinationSum3(3, 9);
        System.out.println(lists);
    }

}
